package com.lxl.todo;

import java.util.HashMap;

/**
* 爬楼梯
* 一次只能爬1 或 2 步
* 现在有n步楼梯 有几种爬法
* */
public class Solution19 {
    private final HashMap<Integer, Integer> map = new HashMap<>();
    public int climbStairs(int n) {
        if (n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        } else {
            map.put(n, climbStairs(n - 1) + climbStairs(n - 2));
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    public static void main(String[] args) {
        Solution19 solution19 = new Solution19();
        System.out.println(solution19.climbStairs(5));
    }
}
